package 排序算法.插入排序;
//二分插入排序
//算法的移动次数与直接插入排序算法的相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)。
//1、基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。
public class Binary_Sort {
    public static void main(String[] args) {
        int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
        sort(a);
    }

    private static void sort(int[] a){
        if (a == null || a.length == 0) {
            return;
        }
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }

        for (int i=0;i<a.length;i++){
            int right=i-1;
            int left=0;
            int mid=0;
            int temp=a[i];
            //二分法 二分查找最佳插入位置
            while (left<=right){
                mid=(left+right)/2;
                if(temp<a[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
            //直接插入排序方法类似
            for(int j=i-1;j>=left;j--){
                a[j+1]=a[j];
            }
            if(left!=i){
                a[left]=temp;
            }

        }
        System.out.println("\n排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }

    }
}
